# 给你一个链表数组，每个链表都已经按升序排列。 
# 
#  请你将所有链表合并到一个升序链表中，返回合并后的链表。 
# 
#  
# 
#  示例 1： 
# 
#  输入：lists = [[1,4,5],[1,3,4],[2,6]]
# 输出：[1,1,2,3,4,4,5,6]
# 解释：链表数组如下：
# [
#   1->4->5,
#   1->3->4,
#   2->6
# ]
# 将它们合并到一个有序链表中得到。
# 1->1->2->3->4->4->5->6
#  
# 
#  示例 2： 
# 
#  输入：lists = []
# 输出：[]
#  
# 
#  示例 3： 
# 
#  输入：lists = [[]]
# 输出：[]
#  
# 
#  
# 
#  提示： 
# 
#  
#  k == lists.length 
#  0 <= k <= 10^4 
#  0 <= lists[i].length <= 500 
#  -10^4 <= lists[i][j] <= 10^4 
#  lists[i] 按 升序 排列 
#  lists[i].length 的总和不超过 10^4 
#  
# 
#  Related Topics 链表 分治 堆（优先队列） 归并排序 👍 2934 👎 0
import heapq
import sys
from typing import Optional, List

from LeetCode.Test.LinkTool import ListNode, LinkedListTool, Link


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        """
        方法1:利用python的最小堆来实现快速拿出最小的节点
        :param lists:
        :return:

        dummy = ListNode(-1)
        curr = dummy
        heap = []
        index = 0
        for node in lists:
            if node:
                # 放入一个(node.val,node)元组到堆，这样堆会默认以元组第一个参数排序
                heapq.heappush(heap, (node.val, index, node))
                index += 1
        while heap:
            val,_,min_node = heapq.heappop(heap)
            curr.next = min_node
            curr = curr.next
            # 如果取出来的还有支链，那么支链依然要放入堆中和其它的节点相比较
            if min_node.next:
                heapq.heappush(heap, (min_node.next.val, index, min_node.next))
                index += 1
        return dummy.next
        """
        """
        运用递归分成2个两个比较
        """
        """
        if not lists:
            return None
        if len(lists) == 1:
            return lists[0]

        mid = len(lists) // 2
        # 递归左半部分
        left = self.mergeKLists(lists[:mid])
        # 递归右半部分
        right = self.mergeKLists(lists[mid:])
        return mergeTwoLists(left, right)


def mergeTwoLists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    dummy = ListNode(-1)
    curr = dummy
    while list1 and list2:
        if list1.val > list2.val:
            next_node2 = list2.next
            # 把小的移动到dummy后面
            curr.next = list2
            list2.next = None
            # 移动list2指针
            list2 = next_node2
        else:
            next_node1 = list1.next
            curr.next = list1
            list1.next = None
            # 移动list1指针
            list1 = next_node1
        curr = curr.next
    # 检查哪个还有剩余,把剩余的直接接到后面就行了
    if list1:
        curr.next = list1
    if list2:
        curr.next = list2
    return dummy.next
"""
        """
        方法三：用heapq.merge方法
        """
        # 生成器是一种惰性求值的迭代器，它在被迭代时才生成值，适合处理大数据以节省内存。
        def lists_value(node):
            while node:
                yield node.val
                node = node.next
        # 返回一个生成器
        merged_values = heapq.merge(*[lists_value(node) for node in lists])
        dummy = ListNode(-1)
        curr = dummy
        # 迭代生成器
        for value in merged_values:
            curr.next = ListNode(value)
            curr = curr.next
        return dummy.next
# leetcode submit region end(Prohibit modification and deletion)
Link.each(Solution().mergeKLists(
    [LinkedListTool([1, 3, 5, 7, 9]), LinkedListTool([2, 4, 6, 8, 10]), LinkedListTool([1, 2, 3, 5, 9])]))
